package queue;

import queue.CandyQueue;

/**
 * 
 * @Title: LoopQueue.java 
 * @Package stack 
 * @Description: 自定义一个循环队列
 * @author CandyWall   
 * @date 2020年12月19日 下午12:55:40 
 * @version V1.0
 */
public class CandyLoopQueue_v1<E> implements CandyQueue<E> {
	private E[] data;
	private int front, rear;
	private int size;
	
	public CandyLoopQueue_v1() {
		this(10);
	}
	
	public CandyLoopQueue_v1(int capacity) {
		data = (E[]) new Object[capacity + 1];
		front = 0;
		rear = 0;
		size = 0;
	}

	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return front == rear;
	}

	@Override
	public void enqueue(E e) {
		if(size == getCapacity()) {
			resize(size << 1);
		}
		
		data[rear] = e;
		rear = (rear + 1) % data.length;
		size++;
	}

	@Override
	public E dequeue() {
		E e = data[front];
		front = (front + 1) % data.length;
		size--;
		if(size == data.length / 4) {
			resize(size >> 1);
		}
		return e;
	}
	
	/**
	 * 队列扩容或者缩容
	 * @param newCapacity
	 */
	private void resize(int newCapacity) {
		E[] newArray = (E[]) new Object[newCapacity + 1];
		//将队列中的元素出队，依次存到新队列中
		for(int i = 0, j = front; i < size; i++, j = (j + 1) % data.length) {
			newArray[i] = data[j]; 
		}
		front = 0;
		rear = size;
		data = newArray;
	}

	@Override
	/**
	 * 获取队头元素
	 */
	public E getFront() {
		return data[front];
	}

	@Override
	/**
	 * 获取队列的容量，有一个位置不存放值，用于区别队列为空和队列满的情况，所以需要减去1
	 * @return capacity
	 */
	public int getCapacity() {
		return data.length - 1;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder(String.format("CandyLoopQueue: size = %d, capacity = %d, front [", size, getCapacity()));
		for(int i = 0, j = front; ; i++, j = (j + 1) % data.length) {
			sb.append(data[j]);
			if(i == size - 1)
				return sb.append("] rear").toString();
			sb.append(", ");
		}
	}

	public static void main(String[] args) {
		CandyLoopQueue_v1<Integer> queue = new CandyLoopQueue_v1<>(10);
		for(int i = 0; i < 10; i++) {
			queue.enqueue(i);
			System.out.println(queue);
		}
		
		System.out.println(queue.dequeue());
		System.out.println(queue);
		System.out.println(queue.dequeue());
		System.out.println(queue);
		queue.enqueue(10);
		queue.enqueue(11);
		queue.enqueue(12);
	}

}
